package com.fosss.tree;

/**
 * 线索化二叉树
 */
public class ThreadBinaryTreeDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        ThreadHeroNode root = new ThreadHeroNode(1, "tom");
        ThreadHeroNode node2 = new ThreadHeroNode(3, "jack");
        ThreadHeroNode node3 = new ThreadHeroNode(6, "smith");
        ThreadHeroNode node4 = new ThreadHeroNode(8, "mary");
        ThreadHeroNode node5 = new ThreadHeroNode(10, "king");
        ThreadHeroNode node6 = new ThreadHeroNode(14, "dim");

        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        //测试中序线索化
        ThreadBinaryTree threadedBinaryTree = new ThreadBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.cueingBinaryTree();

        //测试: 以10号节点测试
        ThreadHeroNode leftNode = node5.getLeft();
        ThreadHeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1

        threadedBinaryTree.middleThreadedOrder();// [8,3,10,1,14,6]
    }
}

/**
 * 创建二叉树类
 */
class ThreadBinaryTree {
    private ThreadHeroNode root;
    private ThreadHeroNode pre = null;//代表前驱节点

    public ThreadBinaryTree() {
    }

    public ThreadBinaryTree(ThreadHeroNode root) {
        this.root = root;
    }

    public ThreadHeroNode getRoot() {
        return root;
    }

    public void setRoot(ThreadHeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        }
    }

    //中序遍历
    public void middleOrder() {
        if (this.root != null) {
            this.root.middleOrder();
        }
    }

    //后序遍历
    public void lastOrder() {
        if (this.root != null) {
            this.root.lastOrder();
        }
    }

    //前序遍历查找
    public ThreadHeroNode preSearch(int no) {
        if (this.root == null)
            return null;
        return this.root.preSearch(no);
    }

    //中序遍历查找
    public ThreadHeroNode middleSearch(int no) {
        if (this.root == null)
            return null;
        return this.root.middleSearch(no);
    }

    //后序遍历查找
    public ThreadHeroNode lastSearch(int no) {
        if (this.root == null)
            return null;
        return this.root.lastSearch(no);
    }

    /**
     * 删除指定节点
     */
    public void deleteByNo(int no) {
        if (this.root == null)
            return;
        if (this.root.getNo() == no) {
            this.root = null;
            return;
        }
        this.root.deleteByNo(no);
    }

    /**
     * 中序线索化二叉树
     */
    //重载方法
    public void cueingBinaryTree() {
            cueingBinaryTree(root);
    }

    public void cueingBinaryTree(ThreadHeroNode node) {
        //判断结点是否为空
        if (node == null) {
            return;
        }

        //向左线索化
        cueingBinaryTree(node.getLeft());

        //进行线索化
        //处理前驱结点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        //!!!!!!!!!!!!每处里一个节点后，让前一个结点指向当前节点
        pre = node;

        //向右线索化
        cueingBinaryTree(node.getRight());
    }

    /**
     * 中序遍历线索化后的二叉树
     */
    public void middleThreadedOrder(){
        ThreadHeroNode node=root;

        while (node!=null){
            while (node.getLeftType()==0){
                node=node.getLeft();
            }
            System.out.println(node);

            while (node.getRightType() ==1){
                node=node.getRight();
                System.out.println(node);
            }

            node=node.getRight();
        }
    }
}


/**
 * 创建结点类
 */
class ThreadHeroNode {
    private int no;
    private String name;
    private ThreadHeroNode left;//默认为空
    private ThreadHeroNode right;//默认为空

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    //标志
    private int leftType = 0;//0代表指向左子树，1代表指向前驱结点
    private int rightType = 0;//0代表指向有字数，1代表指向后继结点

    public ThreadHeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ThreadHeroNode getLeft() {
        return left;
    }

    public void setLeft(ThreadHeroNode left) {
        this.left = left;
    }

    public ThreadHeroNode getRight() {
        return right;
    }

    public void setRight(ThreadHeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "ThreadHeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历
    public void preOrder() {
        //先输出当前节点，再向左递归，再向右递归
        System.out.println(this);//谁调用这个方法,this就代表谁
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历
    public void middleOrder() {
        //先向左递归，再输出当前节点，再向右递归
        if (this.left != null) {
            this.left.middleOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.middleOrder();
        }
    }

    //后序遍历
    public void lastOrder() {
        //先向左递归，再向右递归,再输出当前节点
        if (this.left != null) {
            this.left.lastOrder();
        }
        if (this.right != null) {
            this.right.lastOrder();
        }
        System.out.println(this);
    }

    //前序遍历查找
    public ThreadHeroNode preSearch(int no) {
        //先判断当前结点是不是，不是的话向左递归，向右递归
        ThreadHeroNode heroNode = null;

        if (this.no == no) {
            return this;
        }
        if (this.left != null) {
            heroNode = this.left.preSearch(no);
        }
        if (heroNode != null) {//这一步的作用是如果找到，就停止继续查找
            return heroNode;
        }

        if (this.right != null) {
            heroNode = this.right.preSearch(no);
        }
        return heroNode;

    }

    //中序遍历查找
    public ThreadHeroNode middleSearch(int no) {
        //先判断当前结点是不是，不是的话向左递归，向右递归
        ThreadHeroNode heroNode = null;

        if (this.left != null) {
            heroNode = this.left.preSearch(no);
        }
        if (heroNode != null) {//这一步的作用是如果找到，就停止继续查找
            return heroNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            heroNode = this.right.preSearch(no);
        }
        return heroNode;
    }

    //后序遍历查找
    public ThreadHeroNode lastSearch(int no) {
        //先判断当前结点是不是，不是的话向左递归，向右递归
        ThreadHeroNode heroNode = null;

        if (this.left != null) {
            heroNode = this.left.preSearch(no);
        }
        if (heroNode != null) {//这一步的作用是如果找到，就停止继续查找
            return heroNode;
        }

        if (this.right != null) {
            heroNode = this.right.preSearch(no);
        }
        if (this.no == no) {
            return this;
        }
        return heroNode;
    }

    /**
     * 删除  如果是叶子节点就删除该节点，如果是子树，直接将子树删掉了
     */
    public void deleteByNo(int no) {

        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }

        //向左递归
        if (this.left != null) {
            this.left.deleteByNo(no);
        }
        //向右递归
        if (this.right != null) {
            this.right.deleteByNo(no);
        }
    }
}





























